package heap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;



import java.util.Map.Entry;

public class topKFrequent {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        //key是值，value是count
        for(int i : nums){
            map.put(i, map.getOrDefault(i, 0)+1);
        }
        int[] rs = new int[k];
        PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {
                    public int compare(int[] o1, int[] o2) {
                        return o1[1]-o2[1];
                    };
                });
        for (Entry<Integer,Integer> entry : map.entrySet()) {
            if (heap.size()==k) {
                if (heap.peek()[1]<entry.getValue()) {
                    heap.poll();
                    heap.offer(new int[]{entry.getKey(),entry.getValue()});
                }
            }else{
                heap.offer(new int[]{entry.getKey(),entry.getValue()});
            }
        }
        for(int i=0;i<k;i++){
            rs[i]=heap.poll()[0];
        }
        return rs;
        
    }

    public static void main(String[] args) {
        topKFrequent obj = new topKFrequent();
        int[] nums = new int[]{1,1,1,2,2,3};
        // int[] nums = new int[] { 1, 2, 1, 2, 1, 2, 3, 1, 3, 2 };
        int[] arr = obj.topKFrequent(nums, 2);
        for (int item : arr) {
            System.out.println(item);
        }
    }
}
